#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int ElementType;

typedef struct STable
{
    ElementType *elem;
    int len;
} STable;

void printSTable(STable table)
{
    for (int i = 0; i < table.len; i++)
    {
        printf("%3d", table.elem[i]);
    }
    printf("\n");
}

void swap(ElementType &a, ElementType &b)
{
    ElementType tmp = a;
    a = b;
    b = tmp;
}

void bubbleSort(int elem[], int len)
{
    for (int i = 0; i < len - 1; i++)
    {
        for (int j = 0; j < len - 1 - i; j++)
        {
            if (elem[j] > elem[j + 1])
            {
                swap(elem[j], elem[j + 1]);
            }
        }
    }
}

int quickSortHelp(int elem[], int left, int right)
{
    int flag = elem[left];
    while (left < right)
    {
        while (left < right && elem[right] >= flag)
        {
            right--;
        }
        elem[left] = elem[right];
        while (left < right && elem[left] <= flag)
        {
            left++;
        }
        elem[right] = elem[left];
    }
    elem[left] = flag;
    return left;
}

void quickSort(int elem[], int left, int right)
{
    if (left < right)
    {
        int mid = quickSortHelp(elem, left, right);
        quickSort(elem, left, mid - 1);
        quickSort(elem, mid + 1, right);
    }
}

void insertSort(int elem[], int len)
{
    int flag, j;
    for (int i = 0; i < len; i++)
    {
        flag = elem[i];
        for (j = i - 1; j >= 0 && elem[j] > flag; j--)
        {
            elem[j + 1] = elem[j];
        }
        elem[j + 1] = flag;
    }
}

void selectSort(int elem[], int len)
{
    int max_index, j;
    for (int i = 0; i < len - 1; i++)
    {
        max_index = 0;
        for (j = 0; j < len - i; j++)
        {
            if (elem[j] > elem[max_index])
            {
                max_index = j;
            }
        }
        swap(elem[max_index], elem[j - 1]);
    }
}

void mergeSortHelp(int elem[], int left, int mid, int right)
{
    ElementType new_elem[right + 1];
    for (int i = left; i <= right; i++)
    {
        new_elem[i] = elem[i];
    }
    int index_left = left, index_right = mid + 1;
    int index = left;
    while (index_left <= mid && index_right <= right)
    {
        if (new_elem[index_left] <= new_elem[index_right])
        {
            elem[index++] = new_elem[index_left++];
        }
        else
        {
            elem[index++] = new_elem[index_right++];
        }
    }
    while (index_left <= mid)
    {
        elem[index++] = new_elem[index_left++];
    }
    while (index_right <= right)
    {
        elem[index++] = new_elem[index_right++];
    }
}

void mergeSort(int elem[], int left, int right)
{
    if (left < right)
    {
        int mid = (left + right) / 2;
        mergeSort(elem, left, mid);
        mergeSort(elem, mid + 1, right);
        // 合并两个有序数组
        mergeSortHelp(elem, left, mid, right);
    }
}

// 调整成大顶堆
void adjustDown(int elem[], int root_index, int len)
{
    int dad = root_index;
    int son = dad * 2 + 1;
    int tmp;
    while (son < len)
    {
        if (son + 1 < len && elem[son] < elem[son + 1])
        {
            son++;
        }
        if (elem[dad] < elem[son])
        {
            tmp = elem[dad];
            elem[dad] = elem[son];
            elem[son] = tmp;
            dad = son;
            son = dad * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

void heapSort(int elem[], int len)
{
    for (int i = len / 2 - 1; i >= 0; i--)
    {
        adjustDown(elem, i, len);
    }
    int tmp;
    for (int i = len - 1; i > 0; i--)
    {
        tmp = elem[0];
        elem[0] = elem[i];
        elem[i] = tmp;
        adjustDown(elem, 0, i);
    }
}

void initSTable(STable &table, int len)
{
    table.elem = (ElementType *)malloc(sizeof(ElementType) * len);
    table.len = len;
    srand(time(NULL));
    for (int i = 0; i < len; i++)
    {
        table.elem[i] = rand() % 100;
    }
}

int main()
{
    STable table;
    initSTable(table, 10);
    printSTable(table);
    // bubbleSort(table.elem, table.len);
    // quickSort(table.elem, 0, table.len - 1);
    // insertSort(table.elem, table.len);
    // selectSort(table.elem, table.len);
    // mergeSort(table.elem, 0, table.len - 1);
    heapSort(table.elem, table.len);
    printSTable(table);
    return 0;
}